class Solution {
public:
    int _minimumMoves(vector<vector<int>>& grid, vector<pair<int, int>>& from,
        vector<pair<int, int>>& to, int pos, int cost)
    {
        if (pos == to.size())
            return cost;
        int ret = INT_MAX;
        for (auto& p : from)
        {
            if (grid[p.first][p.second] > 1)
            {
                grid[p.first][p.second]--;
                int subCost = abs(p.first - to[pos].first) + abs(p.second - to[pos].second);
                ret = min(ret, _minimumMoves(grid, from, to, pos + 1, subCost + cost));
                grid[p.first][p.second]++;
            }
        }
        return ret;
    }

    int minimumMoves(vector<vector<int>>& grid) {
        vector<pair<int, int>> from, to;
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                if (grid[i][j] > 1)
                    from.push_back(make_pair(i, j));
                if (grid[i][j] == 0)
                    to.push_back(make_pair(i, j));
            }
        }
        return _minimumMoves(grid, from, to, 0, 0);
    }
};